-
-
Photo: John Cairns
Prospective PhD students:
Information about how to apply (to start in Autumn of 2027) is here:
https://www.ox.ac.uk/admissions/graduate/courses/dphil-computer-science.
You can read about my research interests below.
Prospective students should feel free to get in touch if any
of these problems sounds interesting, or if you have other related
ideas in algorithms or complexity theory.
I would encourage you also to read my page on
mathematics and AI because this is especially
relevant to PhD students.
Research Interests
My work is in the intersection of maths and computer science.
Specifically, I work on the design and analysis of randomised algorithms.
Randomised algorithms arise in many computational
contexts including
communication and information spread in networks,
analysing computational models from statistical physics (and other models where
local interactions influence global structure), and learning.
My research focuses on the rigorous, mathematical
analysis of these algorithms - proving
results about how long the algorithms take, and how accurate they are.
I am also interested in related questions from computational complexity
where the goal is to figure out which computational problems can be solved with fast (randomised)
algorithms and which problems provably can't be solved with fast algorithms.
This research is part of the
Algorithms
and Complexity Theory research theme
at Oxford.
Recent results, current projects, and potential PhD projects:
- Contention resolution.
A contention resolution protocol is a simple randomised algorithm which
is used by independent agents to access a shared resource.
These algorithms give rise to difficult and interesting mathematical questions that apply in natural settings.
In the basic model, agents arrive over time, according to a probability
distribution, and have no way to communicate with each other except by attempting to access the resource.
If two agents attempt access at the same time, they "collide" and must try again later. A
backoff protocol is a simple randomised algorithm that agents use to determine when to attempt
access and when to wait. The simplest example is binary exponential backoff
where an agent that has already collided k times makes a random decision at each step,
attempting access with probability
2−k and waiting with probability 1-2-k.
Based on the model of
Frank Kelly,
David Aldous proved that binary exponential backoff is unstable
for any positive rate of arrival,
in the sense that
the underlying random process is not positive recurrent. Informally, this says
that the number of waiting agents builds up over time, even if the rate at which they arrive is arbitrarily low.
Aldous conjectured in 1987 that the same is true for any backoff protocol. After lots of work,
John Lapinskas and I finally proved this in 2026 (the paper is
here). There are lots of interesting open problems, both
in the original model of Kelly, and in other models where contention is
mitigated by the presence of queues, as in
this
paper with
Hesham Al-Ammal and
Phil MacKenzie, or where arrivals are adversarial,
as in this paper by Bender, Kopelowitz, Kuszmaul, and
Pettie.
- Spin systems: sampling and approximate
counting.
One of the most important domains where randomised algorithms are studied is the area of
spin systems. In a spin system, a configuration assigns a "spin" to every vertex of a graph. Spins interact locally along the
edges of the graph, and these interactions give rise to a global distribution on configurations, called the Gibbs
distribution. A famous example is the Ising model. Research in
our area focuses on
determining which model parameters give rise to
fast algorithms for sampling configurations from the Gibbs distribution. Most of my research in this area is joint with
Andreas Galanis and our joint students.
Here is a paper with
our jointly-supervised PhD student,
Paulina Smolarova.
This paper gives a fast algorithm in a setting where the underlying graph is
random (so there are two levels of randomness). Sometimes, it is possible to give fast algorithms on
random graphs in parameter regimes where
it is conjectured that fast algorithms don't exist for worst-case graphs. There are plenty
of open questions about identifying the boundary between where fast algorithms exist and where they don't. Andreas and I are
interested in supervising more PhD students in this area (and related areas).
Many important properties of a spin system can be determined by estimating a function
called its "partition function".
I won't give technical details here, but you can find a very gentle introduction
to a related type of partition function (along with a reference to more of our research in this area)
here
.
The research field that studies algorithms for estimating partition functions is called
"computational counting".
The study of counting complexity goes back
to Les Valiant in the 1970s, but in the
context of randomness and approximation
there are additional challenges.
Here
is an early paper with
Martin Dyer,
Catherine Greenhill, and
Mark Jerrum, which identifies a
key complexity class for approximate counting, centred around a
problem called
#BIS, which is the problem of approximately counting the
independent sets of a bipartite graph. By now there are many
computational problems and classes of computational problems which
are known to be equivalent to #BIS, but we still don't know whether
it even has a fast approximation algorithm (with or without randomness), and this is a
tantalising open problem.
Here is a paper with Jerrum
explaining the relationship between #BIS and spin systems.
- Analysing processes on networks.
Some of my research involves the study of random processes on graphs. For example,
the Moran process is a process which models the spread of genetic mutations in graphs. The goal is to
derive rigorous probabilistic bounds on how these mutations spread over time (as a function of the graph).
Some of my work in the area includes
this paper
(joint with Galanis, Andreas Goebel,
Lapinskas, and
Dave Richerby)
and
this paper (joint with Lapinskas and Richerby).
There are lots of open problems. For example, not much is known when there are several types of mutation, and not much is known about
convergence times on specific families of graphs.
There are also other interesting related models. For example, the voter model, which
models the spread of competing ideas in social networks.
Here
is a recent paper with Galanis and our jointly supervised PhD student
Xandru Mifsud.
analysing a random walk on an evolving random cluster configuration. The random cluster model is another model
related to spin systems. Random walks on randomly evolving environments is a popular research area.
- Approximately counting graph homomorphisms and
related structures
A lot of progress in approximate counting (including randomised
approximate counting) has come from understanding
key graph structures such as
graph homomorphisms.
Often the key ideas come from the study of the structures themselves
(which turn out to be complicated and fascinating!).
Standa Zivny
and I are interesting in jointly superivising a PhD in this area.
Here is a joint paper
with our previous jointly-supervised PhD student
Jacob Focke (and with Marc Roth)
which uses methods related to graph homomorphisms to obtain
approximate-counting results relevant to databases.
A recent paper with Roth (see here)
uses this kind of analysis to deterermine the fine-grained complexity of counting subgraphs, modulo 2.
Links